{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etree_intro_md"
      },
      "source": [
        "# EliminationTree"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etree_desc_md"
      },
      "source": [
        "An `EliminationTree` represents the computational structure of sequential variable elimination (like Gaussian elimination) on a `FactorGraph` given a specific `Ordering`.\n",
        "\n",
        "Each node in the tree corresponds to a variable being eliminated. The children of a node represent variables that were eliminated earlier and produced factors involving the parent variable. The factors originally involving the variable at a node are stored at that node.\n",
        "\n",
        "Eliminating an `EliminationTree` yields a `BayesNet`.\n",
        "\n",
        "While fundamental to the theory, direct manipulation of `EliminationTree` objects in Python is less common than using the `eliminateSequential` method on a `FactorGraph`, which uses the `EliminationTree` internally."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etree_colab_md"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/borglab/gtsam/blob/develop/gtsam/inference/doc/EliminationTree.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "etree_pip_code",
        "tags": [
          "remove-cell"
        ]
      },
      "outputs": [],
      "source": [
        "%pip install --quiet gtsam-develop"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "etree_import_code"
      },
      "outputs": [],
      "source": [
        "import gtsam\n",
        "import numpy as np\n",
        "\n",
        "# EliminationTree is templated, need concrete types\n",
        "from gtsam import GaussianFactorGraph, Ordering, GaussianEliminationTree, GaussianBayesNet\n",
        "from gtsam import symbol_shorthand\n",
        "\n",
        "X = symbol_shorthand.X\n",
        "L = symbol_shorthand.L"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etree_create_md"
      },
      "source": [
        "## Creating an EliminationTree\n",
        "\n",
        "An `EliminationTree` is constructed from a `FactorGraph` and an `Ordering`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "etree_create_code",
        "outputId": "f0123456-789a-bcde-f012-3456789abcde"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Elimination Tree: -(x2)\n",
            "Elimination Tree: | -(l2)\n",
            "Elimination Tree: | -\n",
            "  A[l2] = [\n",
            "\t-1\n",
            "]\n",
            "  A[x2] = [\n",
            "\t1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n",
            "Elimination Tree: | | -(x1)\n",
            "Elimination Tree: | | -\n",
            "  A[x1] = [\n",
            "\t-1\n",
            "]\n",
            "  A[x2] = [\n",
            "\t1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n",
            "Elimination Tree: | | -\n",
            "  A[l2] = [\n",
            "\t-1\n",
            "]\n",
            "  A[x1] = [\n",
            "\t1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n",
            "Elimination Tree: | | | -(l1)\n",
            "Elimination Tree: | | | -\n",
            "  A[l1] = [\n",
            "\t-1\n",
            "]\n",
            "  A[x1] = [\n",
            "\t1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n",
            "Elimination Tree: | | | | -(x0)\n",
            "Elimination Tree: | | | | -\n",
            "  A[x0] = [\n",
            "\t-1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n",
            "Elimination Tree: | | | | -\n",
            "  A[x0] = [\n",
            "\t-1\n",
            "]\n",
            "  A[x1] = [\n",
            "\t1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n",
            "Elimination Tree: | | | | -\n",
            "  A[l1] = [\n",
            "\t-1\n",
            "]\n",
            "  A[x0] = [\n",
            "\t1\n",
            "]\n",
            "  b = [ 0 ]\n",
            "  Noise model: unit (1) \n"
          ]
        }
      ],
      "source": [
        "# Create a graph (same as BayesTree example)\n",
        "graph = GaussianFactorGraph()\n",
        "model = gtsam.noiseModel.Isotropic.Sigma(1, 1.0)\n",
        "graph.add(X(0), -np.eye(1), np.zeros(1), model)\n",
        "graph.add(X(0), -np.eye(1), X(1), np.eye(1), np.zeros(1), model)\n",
        "graph.add(X(1), -np.eye(1), X(2), np.eye(1), np.zeros(1), model)\n",
        "graph.add(L(1), -np.eye(1), X(0), np.eye(1), np.zeros(1), model)\n",
        "graph.add(L(1), -np.eye(1), X(1), np.eye(1), np.zeros(1), model)\n",
        "graph.add(L(2), -np.eye(1), X(1), np.eye(1), np.zeros(1), model)\n",
        "graph.add(L(2), -np.eye(1), X(2), np.eye(1), np.zeros(1), model)\n",
        "\n",
        "# Define an ordering\n",
        "ordering = Ordering([X(0), L(1), X(1), L(2), X(2)])\n",
        "\n",
        "# Construct the Elimination Tree\n",
        "elimination_tree = GaussianEliminationTree(graph, ordering)\n",
        "\n",
        "elimination_tree.print(\"Elimination Tree: \")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "etree_eliminate_md"
      },
      "source": [
        "## Elimination\n",
        "\n",
        "The primary use of an `EliminationTree` is to perform sequential elimination to produce a `BayesNet`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "etree_eliminate_code",
        "outputId": "01234567-89ab-cdef-0123-456789abcdef"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "BayesNet from EliminationTree:\n",
            "\n",
            "size: 5\n",
            "conditional 0:  p(x0 | l1 x1)\n",
            "  R = [ 1.73205 ]\n",
            "  S[l1] = [ -0.57735 ]\n",
            "  S[x1] = [ -0.57735 ]\n",
            "  d = [ 0 ]\n",
            "  logNormalizationConstant: -0.369632\n",
            "  No noise model\n",
            "conditional 1:  p(l1 | x1)\n",
            "  R = [ 1.29099 ]\n",
            "  S[x1] = [ -1.0328 ]\n",
            "  d = [ 0 ]\n",
            "  logNormalizationConstant: -0.663526\n",
            "  No noise model\n",
            "conditional 2:  p(x1 | l2 x2)\n",
            "  R = [ 1.61245 ]\n",
            "  S[l2] = [ -0.620174 ]\n",
            "  S[x2] = [ -0.620174 ]\n",
            "  d = [ 0 ]\n",
            "  logNormalizationConstant: -0.441183\n",
            "  No noise model\n",
            "conditional 3:  p(l2 | x2)\n",
            "  R = [ 1.27098 ]\n",
            "  S[x2] = [ -1.08941 ]\n",
            "  d = [ 0 ]\n",
            "  logNormalizationConstant: -0.679152\n",
            "  No noise model\n",
            "conditional 4:  p(x2)\n",
            "  R = [ 0.654654 ]\n",
            "  d = [ 0 ]\n",
            "  mean: 1 elements\n",
            "  x2: 0\n",
            "  logNormalizationConstant: -1.34259\n",
            "  No noise model\n"
          ]
        }
      ],
      "source": [
        "# The eliminate function needs to be specified (e.g., EliminateGaussian)\n",
        "# In Python, this is usually handled internally by graph.eliminateSequential\n",
        "# but the C++ EliminationTree has an eliminate method.\n",
        "\n",
        "# Let's call the graph's eliminateSequential which uses the tree internally\n",
        "bayes_net, remaining_graph = graph.eliminatePartialSequential(ordering)\n",
        "\n",
        "print(\"BayesNet from EliminationTree:\")\n",
        "bayes_net.print()"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "gtsam",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.13.1"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
